ESPACIOP-completo

ESPACIOP-completo: En teoría de la complejidad computacional, la clase de complejidad ESPACIOP-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en ESPACIOP y todo problema en ESPACIOP puede ser reducido a él en tiempo polinomial. Los problemas en ESPACIOP-completo pueden verse como los problemas más difíciles de la clase ESPACIOP. Se sospecha fuertemente que estos problemas están fuera de las clases de complejidad P y NP, pero no hay prueba de ello. Se sabe que no están contenidos en la clase NC.

Игры ⚽ Нужно решить контрольную?

ESPACIOP — Saltar a navegación, búsqueda En teoría de la complejidad computacional, la clase ESPACIOP (PSPACE en inglés) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial (S(n) … Wikipedia Español
Clases de complejidad — Anexo:Clases de complejidad Saltar a navegación, búsqueda Esta es la lista de clases de complejidad en teoría de la complejidad computacional. Muchas de estas clases tienen una co clase que contiene los problemas complementarios a los de la clase … Wikipedia Español
Clase de complejidad — En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Una clase de complejidad tiene una definición de la forma: el conjunto de los problemas de decisión que pueden … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico